1237D - Balanced Playlist - CodeForces Solution

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
#include <functional>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
#include <functional>
#include <iomanip>
#include <numeric>

#pragma GCC optimize("Ofast,inline,unroll-loops")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,bmi2,fma")
#define int long long
#define rep(i, a, b) for(int i = a; i < b; i++)
#define per(i, a, b) for(int i = b; i > b; i--)
#define pre(i) while(i--)
#define elif else if
#define vec vector
#define print(x, s) for(auto e : x) cout << e << s;
#define all(x) x.begin(), x.end()
#define read(a) for(auto& e : a) cin >> e;
#define ub upper_bound
#define lb lower_bound
#define pii pair<int, int>
#define x first
#define y second
//#define push push_back

#ifdef _MSC_VER
#include <intrin.h>
#define __builtin_popcount __popcnt
#define __int128 int64_t
#endif

using namespace std;
using lint = long long;
using str = string;

template<typename T>
int sum(vec<T>& a) { int sume = a[0]; for (int i = 1; i < a.size(); i++) sume += a[i]; return sume; }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

vec<bool> to_bin(int n, int count_bit = -1) {
	vec<bool> res;
	while (n) {
		res.push_back(n % 2);
		n /= 2;
	}
	reverse(all(res));
	return res;
}

int all_gcd(vec<int> a) {
	int ans = a[0];
	for (auto e : a) ans = gcd(e, ans);
	return ans;
}

const int mod = 998244353, SZ = 3010, INF = 1e18, LIMIT = 5e6;

int bin_pow(int a, int b) {
	int res = 1;
	while (b) {
		if (b & 1) res = 1ll * res * a % mod;
		a = 1ll * a * a % mod;
		b /= 2;
	}
	return res;
}

class DisjointSparseTableMAX {
public:
	int m;
	int f(int e, int p = INT64_MIN) {
		return max(e, p);
	}
	vector<vector<int>> st;
	vector<int> logs;
	void build(vector<int> a, int n, int M = 0) {
		int len = 1;
		m = M;
		while ((1ll << len) < n) len += 1;
		a.resize((1ll << len), 1);
		logs.resize((1ll << len), 0);
		st = vector<vector<int>>(len + 1, vector<int>(1ll << len));
		st[0][0] = a[0];
		for (int i = 1; i < (1ll << len); i++) st[0][i] = f(a[i]), logs[i] = log2(i);
		for (int h = 1; h < len; h++) {
			int tlen = (1ll << h);
			for (int c = tlen; c < (1ll << len); c += 2 * tlen) {
				st[h][c] = a[c];
				for (int i = c + 1; i < c + tlen; i++) {
					st[h][i] = f(st[h][i - 1], a[i]);
				}
				st[h][c - 1] = a[c - 1];
				for (int i = c - 2; i >= c - tlen; i--) {
					st[h][i] = f(st[h][i + 1], a[i]);
				}
			}
		}
	}
	int ans(int l, int r) {
		if (l == r) return f(st[0][l]);
		int row = logs[l ^ r];
		return f(st[row][l], st[row][r]);
	}
};

void init() {
	//cout << fixed << setprecision(30);
}

void work(int TST) {
	int n; cin >> n;
	vec<int> a(n);
	read(a);
	vec<int> b = a;
	for (int i = 0; i < n; i++) b.push_back(a[i]);
	for (int i = 0; i < n; i++) b.push_back(a[i]);
	int m = 3 * n;
	DisjointSparseTableMAX MX; MX.build(b, m);
	int prev = 1;
	bool was_broke = 0;
	for (int i = 0; i < n; i++) {
		if (prev == i) prev = i + 1;
		for (int j = prev; j < m; j++) {
			if (b[j] < (MX.ans(i, j) + 1) / 2) {
				was_broke = 1;
				prev = j;
				break;
			}
		}
		if (!was_broke) cout << "-1 ", prev = m;
		else cout << prev - i << ' ';
		was_broke = 0;
	}
}


int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	init();
	int t = 1; //cin >> t;
	pre(t) {
		work(t); cout << '\n';
	}
}